<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title>全序关系 - 读论文</title>


        <!-- Custom HTML head -->
        
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="favicon.svg">
        <link rel="shortcut icon" href="favicon.png">
        <link rel="stylesheet" href="css/variables.css">
        <link rel="stylesheet" href="css/general.css">
        <link rel="stylesheet" href="css/chrome.css">
        <link rel="stylesheet" href="css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="highlight.css">
        <link rel="stylesheet" href="tomorrow-night.css">
        <link rel="stylesheet" href="ayu-highlight.css">

        <!-- Custom theme stylesheets -->

        <!-- MathJax -->
        <script async type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
    </head>
    <body>
        <!-- Provide site root to javascript -->
        <script type="text/javascript">
            var path_to_root = "";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded affix "><a href="chapter_1.html">读论文活动</a></li><li class="chapter-item expanded affix "><li class="part-title">6.824 分布式系统</li><li class="chapter-item expanded "><a href="Mapreduce.html"><strong aria-hidden="true">1.</strong> Mapreduce</a></li><li class="chapter-item expanded "><a href="GFS.html"><strong aria-hidden="true">2.</strong> GFS</a></li><li class="chapter-item expanded "><a href="VM-FT.html"><strong aria-hidden="true">3.</strong> VM-FT</a></li><li class="chapter-item expanded "><a href="Raft.html"><strong aria-hidden="true">4.</strong> Raft</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="Raft0.html"><strong aria-hidden="true">4.1.</strong> 感性认识Raft</a></li><li class="chapter-item expanded "><a href="Raft1.html"><strong aria-hidden="true">4.2.</strong> 什么是Raft？</a></li><li class="chapter-item expanded "><a href="Raft2.html"><strong aria-hidden="true">4.3.</strong> 复制状态机（Replicated State Machine）</a></li><li class="chapter-item expanded "><a href="Raft3.html"><strong aria-hidden="true">4.4.</strong> What's wrong with Paxos?</a></li><li class="chapter-item expanded "><a href="Raft4.html"><strong aria-hidden="true">4.5.</strong> 向可理解性进军</a></li><li class="chapter-item expanded "><a href="Raft5.html"><strong aria-hidden="true">4.6.</strong> Raft共识算法（零）</a></li><li class="chapter-item expanded "><a href="Raft6.html"><strong aria-hidden="true">4.7.</strong> Raft共识算法（一）——基础概念</a></li><li class="chapter-item expanded "><a href="Raft7.html"><strong aria-hidden="true">4.8.</strong> Raft共识算法（二）——选举leader</a></li><li class="chapter-item expanded "><a href="Raft8.html"><strong aria-hidden="true">4.9.</strong> Raft共识算法（三）——日志备份（log replication）</a></li><li class="chapter-item expanded "><a href="Raft9.html"><strong aria-hidden="true">4.10.</strong> Raft共识算法（四）——安全性和选举限制</a></li><li class="chapter-item expanded "><a href="Raft10.html"><strong aria-hidden="true">4.11.</strong> Raft共识算法（五）——如何提交之前term里的entry</a></li><li class="chapter-item expanded "><a href="Raft11.html"><strong aria-hidden="true">4.12.</strong> Raft共识算法（六）——安全性定理</a></li><li class="chapter-item expanded "><a href="Raft12.html"><strong aria-hidden="true">4.13.</strong> Raft共识算法（七）——如果follower/candidate宕机了</a></li><li class="chapter-item expanded "><a href="Raft13.html"><strong aria-hidden="true">4.14.</strong> Raft共识算法（八）——时间与可用性</a></li><li class="chapter-item expanded "><a href="Raft14.html"><strong aria-hidden="true">4.15.</strong> 成员变更</a></li><li class="chapter-item expanded "><a href="Raft15.html"><strong aria-hidden="true">4.16.</strong> 日志压缩</a></li><li class="chapter-item expanded "><a href="Raft16.html"><strong aria-hidden="true">4.17.</strong> 与Client的交互</a></li><li class="chapter-item expanded "><a href="Raft17.html"><strong aria-hidden="true">4.18.</strong> 实验时遇到的bug</a></li><li class="chapter-item expanded "><a href="Raft18.html"><strong aria-hidden="true">4.19.</strong> 总结</a></li></ol></li><li class="chapter-item expanded "><a href="Zookeeper.html"><strong aria-hidden="true">5.</strong> Zookeeper</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="linearizability1.html"><strong aria-hidden="true">5.1.</strong> 线性一致性（一）——基础概念</a></li><li class="chapter-item expanded "><a href="linearizability2.html"><strong aria-hidden="true">5.2.</strong> 线性一致性（二）——细究linearizability</a></li><li class="chapter-item expanded "><a href="zk_intro.html"><strong aria-hidden="true">5.3.</strong> 引言</a></li><li class="chapter-item expanded "><a href="zk_service.html"><strong aria-hidden="true">5.4.</strong> Zookeeper Service</a></li><li class="chapter-item expanded "><a href="zk_api.html"><strong aria-hidden="true">5.5.</strong> Zookeeper API</a></li><li class="chapter-item expanded "><a href="zk_prop.html"><strong aria-hidden="true">5.6.</strong> Zookeeper的性质</a></li><li class="chapter-item expanded "><a href="zk_ex.html"><strong aria-hidden="true">5.7.</strong> 基于Zookeeper实现锁</a></li></ol></li><li class="chapter-item expanded "><a href="CRAQ.html"><strong aria-hidden="true">6.</strong> CRAQ</a></li><li class="chapter-item expanded "><a href="lamport_clock.html"><strong aria-hidden="true">7.</strong> Time, Clocks, and the Ordering of Events in a Distributed System</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="lamport_clock1.html"><strong aria-hidden="true">7.1.</strong> 引言</a></li><li class="chapter-item expanded "><a href="lamport_clock_partial_order.html"><strong aria-hidden="true">7.2.</strong> 偏序关系</a></li><li class="chapter-item expanded "><a href="lamport_logic_clock.html"><strong aria-hidden="true">7.3.</strong> 逻辑时钟</a></li><li class="chapter-item expanded "><a href="lamport_total_order.html" class="active"><strong aria-hidden="true">7.4.</strong> 全序关系</a></li><li class="chapter-item expanded "><a href="lamport_clock_ana_behave.html"><strong aria-hidden="true">7.5.</strong> 异常事件</a></li><li class="chapter-item expanded "><a href="lamport_p_clock.html"><strong aria-hidden="true">7.6.</strong> 物理时钟</a></li><li class="chapter-item expanded "><a href="lamport_end.html"><strong aria-hidden="true">7.7.</strong> 结论</a></li></ol></li><li class="chapter-item expanded "><li class="part-title">6.828 操作系统</li><li class="chapter-item expanded "><a href="828intro.html"><strong aria-hidden="true">8.</strong> Killer of Microseconds</a></li><li class="chapter-item expanded "><a href="cloudlab.html"><strong aria-hidden="true">9.</strong> CloudLab</a></li><li class="chapter-item expanded "><a href="dpdk.html"><strong aria-hidden="true">10.</strong> DPDK</a></li><li class="chapter-item expanded "><a href="spdk.html"><strong aria-hidden="true">11.</strong> SPDK</a></li><li class="chapter-item expanded "><a href="Shenango.html"><strong aria-hidden="true">12.</strong> Shenango</a></li><li class="chapter-item expanded "><a href="TritonSort.html"><strong aria-hidden="true">13.</strong> TritonSort</a></li><li class="chapter-item expanded "><a href="Profiling.html"><strong aria-hidden="true">14.</strong> Profiling a warehouse-scale computer</a></li><li class="chapter-item expanded affix "><li class="part-title">6.828 - Network</li><li class="chapter-item expanded affix "><li class="part-title">CS244 - Advanced Topics in Networking</li><li class="chapter-item expanded "><a href="DARPA_NET.html"><strong aria-hidden="true">15.</strong> The Design Philosophy of The DARPA Internet Protocols</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="DARPA_NET2.html"><strong aria-hidden="true">15.1.</strong> Second Level Goals</a></li><li class="chapter-item expanded "><a href="DARPA_NET3.html"><strong aria-hidden="true">15.2.</strong> Types of Service</a></li><li class="chapter-item expanded "><a href="DARPA_NET4.html"><strong aria-hidden="true">15.3.</strong> Varieties of Networks</a></li><li class="chapter-item expanded "><a href="DARPA_NET5.html"><strong aria-hidden="true">15.4.</strong> Architecture and Implementation</a></li><li class="chapter-item expanded "><a href="DARPA_NET6.html"><strong aria-hidden="true">15.5.</strong> Datagrams</a></li></ol></li><li class="chapter-item expanded "><li class="part-title">最后</li><li class="chapter-item expanded "><a href="end.html"><strong aria-hidden="true">16.</strong> 最后</a></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">读论文</h1>

                    <div class="right-buttons">
                        <a href="print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="给所有事件排一个全序关系"><a class="header" href="#给所有事件排一个全序关系">给所有事件排一个全序关系</a></h1>
<h2 id="全序关系"><a class="header" href="#全序关系">全序关系</a></h2>
<p>我们可以使用满足Clock Condition的系统时钟，给系统里所有的事件排一个全序关系。<br />
只要简单地根据这些事件发生的时间进行排序就好了。为了避免两个进程的时间戳相同，我们先给所有进程指定一个全序关系。<br />
准确地说，我们给出如下定义：</p>
<blockquote>
<p>如果a是进程\(P_i \)的事件，b是进程\(P_j \)的事件，记\(a \Rightarrow b\)的条件为</p>
<ol>
<li>\(C_i\langle a\rangle &lt; C_j \langle b\rangle
\)，或者</li>
<li>\(C_i\langle a\rangle = C_j \langle b\rangle \)并且\(P_i&lt;P_j \)</li>
</ol>
</blockquote>
<p>根据上述定义，我们很容易就可以得到系统中所有事件的全序关系，且Clock Condition意味着如果\(a \rightarrow b\)则有\(a \Rightarrow b\)。<br />
换句话说，使用关系符号\( \Rightarrow\)，可以完成&quot;happened before&quot;这种偏序关系到全序关系的转换。</p>
<p>\(\Rightarrow\)顺序取决于系统的时钟\(C_i
\)，在满足Clock Condition的情况下，不同的时钟会导致不同的\(\Rightarrow\)顺序。<br />
给定任何一个由\(\Rightarrow\)确定的全序关系，都会存在一系列的系统时钟能够满足Clock Condition，从而才有可能形成这种全序关系。<br />
在系统的事件中，只有偏序关系\(\rightarrow\)是唯一确定的，而\(\Rightarrow\)这种全序关系则依赖于时钟的选择。</p>
<h2 id="分布式锁"><a class="header" href="#分布式锁">分布式锁</a></h2>
<p>对于实现一个分布式系统来说，如果能维护一个全序关系，则必然是极好的。事实上，我们之所以要实现一个这样的具有正确性的系统逻辑时钟，就是为了获取一个全序关系。接下来，我们将论述如何使用这种事件的全序关系，来解决数据的互斥访问问题。<br />
假设一个系统里，有固定数目的进程，进程之间共享同一组资源。同一时间内，只有一个进程可以使用该资源，因此进程之间必须采取某种同步措施来避免冲突。<br />
我们希望能够找到一种算法，可以保证一个进程访问资源的时候满足如下三个条件：</p>
<blockquote>
<ol>
<li>一个拥有资源的进程能够将该资源授权给另一个进程的前提是，它必须要先释放该资源。</li>
<li>当有多个不同的请求访问该资源的时候，授予访问权限的顺序必须和请求被创建的顺序保持一致。</li>
<li>如果所有进程获取资源之后，会保证最终一定能够释放它，则所有获取资源的请求都会被授予资源的权限。</li>
</ol>
</blockquote>
<p>我们假定初始的时候，有一个特定的进程持有资源。<br />
这些要求都很显然，它们保证了算法的正确性。不过如果将这些条件应用到系统中事件的顺序性当中，<strong>条件2</strong>其实没有说如果两个并发请求同时过来，我们应该先处理哪一个请求。</p>
<p>这是一个nontrivial的问题，换言之，它很重要。
我们是否能安排一个一个scheduling process作为中心节点，来确保请求的顺序性呢？不行，除非我们做一些额外的规定。<br />
假设\(P_0 \)是这个scheduling process，\(P_1 \)先给\(P_0 \)发送请求，再给\(P_2 \)发送消息。在\(P_2
\)接收消息的过程中，它也发送请求给了\(P_0 \)。<br />
那就有可能存在\(P_2 \)的请求比\(P_1 \)的请求先一步到达\(P_0 \)的情形。<br />
在这种情形下，如果\(P_2 \)的请求先一步被授权，则违反了上述条件2。</p>
<p>为了解决该问题，我们引入上一章节的逻辑时钟，该逻辑时钟满足IR1和IR2两个条件。使用逻辑时钟，就可以给所有时间定义一个\(\Rightarrow\)全序关系。<br />
可以用逻辑时钟给所有请求和释放资源的操作维护一个全序关系，有了这个全序关系，我们就可以正确地实现分布式锁的算法。只要确保每个进程都能够知晓其他进程的操作就可以了。</p>
<p>为了简化问题，我们做一些额外的假设。<br />
这些假设不是必须的，但是有了这些假设以后，我们可以不必陷入具体的实现细节。假设\(P_i \)和\(P_j \)是系统里的任意两个进程，\(P_i \)到\(P_j \)的所有消息的接收顺序都与它们的发送顺序保持一致。<br />
进一步地，我们还假设所有发出去的消息最终都能够被收到。（如果我们给消息加上序列号，并且加上message acknowledgement protocol，就不需要再做上述假设了。）</p>
<blockquote>
<p>（额外的话：即消息不会乱序到达，也不会丢失。话说这不是TCP吗？）</p>
</blockquote>
<p>我们还假设任意一个进程都可以直接给其他的进程发送消息。</p>
<p>每个进程自身都维护了一个请求队列，除了它自己以外，其他进程无法看到这个队列。<br />
我们假设请求队列初始的时候，包含一条消息\(T_0 \)：\(P_0 \)请求资源；<br />
\( P_0 \)是上文提到的那个一开始拿到资源的进程，\(T_0 \)是比系统的任何一个逻辑时钟初始值都要小的一个时间戳。</p>
<blockquote>
<p>（注意这个请求队列说的不是HTTP Request，是请求资源的Request命令。）</p>
</blockquote>
<p>接着该算法定义了如下五条规则。为了方便起见，每一条规则定义的动作都可以看作是一个单一的事件。</p>
<ol>
<li>
<p>进程\(P_i \)如果要获取资源，需要发送一个消息\(T_m \)：\(P_i \)请求资源，并把这个消息发送给所有进程；<br />
然后将该消息放到自己的请求队列里面，\(T_m \)是这条消息的时间戳。</p>
</li>
<li>
<p>当\(P_j \)收到包含内容为\(P_i \)请求资源的消息\(T_m \)时，它将这条消息放到它的请求队列里面，并且给\(P_i \)发送一个确认消息（带时间戳的）。 </p>
</li>
<li>
<p>如果进程\(P_i \)要释放资源，它需要把请求队列里的包含\(P_i \)请求资源的\(T_m \)消息移除，并给其他所有进程发送一条带时间戳的\(P_i \)释放资源的消息。</p>
</li>
<li>
<p>当进程\(P_j \)收到\(P_i \)释放资源的消息之后，它就把它请求队列里所有包含\(P_i \)请求资源的消息\(T_m \)移除。</p>
</li>
<li>
<p>当如下两个条件满足的时候，进程\(P_i \)就获取到了资源的使用权：</p>
<ul>
<li><strong>(i)</strong> 在它的请求队列中，存在一个包含\(P_i \)请求资源内容的消息\(T_m \)，在全序关系\(\Rightarrow\)的定义下，该消息比任何其他请求的时间戳都要早。<br />
（To define the relation &quot;\(\Rightarrow\)&quot; for messages, we identify a message with the event of sending it.）<br />
即按照全序关系\(\Rightarrow\)排列后，该请求资源的命令位于请求队列的头部。</li>
<li><strong>(ii)</strong> \(P_i \)从剩下的所有进程里，都收到了一条比\(T_m \)要晚的消息。</li>
</ul>
</li>
</ol>
<blockquote>
<p>注意：第五条规则的条件(i)(ii)判断，是在进程本地进行的。</p>
</blockquote>
<p>我们可以很容易地验证由上述规则定义的算法能够满足上文提到的条件1、2、3。</p>
<p>首先，观察规则5的条件(ii)，我们前文提到有一个假设是消息都是按序接收的，如此则保证了\(P_i \)在处理它自己当前收到的请求的时候，它知道这个请求之前所有请求的信息。</p>
<p>由于只有满足规则3或者规则4，才可以将消息从请求队列里移除，那很容易能够得出条件1是能够满足的。</p>
<p>根据全序关系\(\Rightarrow\)是由偏序关系\(\rightarrow\)拓展得来的这一事实，那么条件2也满足。</p>
<p>规则2确保了在\(P_i \)请求资源之后，系统的状态最终一定会满足规则5的条件(ii)。</p>
<p>规则3和规则4还意味着：如果拿到资源的进程最终一定会释放它，那么规则5的条件2则最终一定会满足，因此条件3成立。</p>
<h2 id="状态机"><a class="header" href="#状态机">状态机</a></h2>
<p>这就是我们给出的分布式算法。<br />
每个独立的进程都遵守这些规则，没有一个作为中心节点/中心存储的进程对资源进行同步。</p>
<p>The synchronization is specified in terms of a State Machine, consisting of a set \(C\) of possible commands, a set \(S\) of possible states, and a function \(e\): \(C×S \rightarrow S\).<br />
The relation \(e(C, S) = S'\) means that executing the command \(C\) with the machine in state \(S\) causes the machine state to change to \(S'\). </p>
<p>在我们的例子里，命令集合C包含了所有\(P_i \)请求资源、\(P_i \)释放资源的命令，状态集合包含了请求队列中所有等待处理的请求命令。</p>
<p>那么当前谁持有资源呢？答案是请求队列里时间戳最小的那个请求的进程（位于队列头节点的），持有了当前资源。<br />
如果要执行一个请求资源的命令，则需要将该请求放到请求队列里的尾部；如果要执行释放资源的命令，则将请求该资源的命令从请求队列里移除。</p>
<p>每个进程都独立地维护着这个状态机，并且处理来自其他进程的命令。因为这些命令都是带时间戳的，因此我们可以根据它们的\(\Rightarrow\)关系达成同步。因此每个进程都执行着相同的一组命令序列。一个进程执行带时间戳为T的条件是：它知晓所有小于T的命令都已经得到了处理。这个算法是很直观的，我们就不再浪费时间去描述它了。</p>
<h2 id="宕机问题"><a class="header" href="#宕机问题">宕机问题</a></h2>
<p>这种方法可以解决分布式系统中，进程的同步问题。然而，这个算法需要系统中所有的进程参与。一个进程必须知道其他所有进程所发出的命令，因此只要有一个进程宕机了，就有可能导致状态机里其他的进程无法正常执行命令，从而导致系统不可用。</p>
<p>宕机问题是一个很严重的事情，不过这超出了这本论文的讨论范围。<br />
We will just observe that the entire concept of failure is only meaningful in the context of physical time.<br />
Without physical time, there is no way to distinguish a failed process from one which is just pausing between events.<br />
用户之所以认为系统“宕机”了，是因为ta认为ta等待响应的时间太长了。<br />
我们在文献《Lamport, L. The implementation of reliable distributed multiprocess systems. To appear in Computer Networks.》中讨论了如何在进程出现故障的情况下，继续让系统工作的方法。</p>
<h2 id="额外的话"><a class="header" href="#额外的话">额外的话</a></h2>
<p>这一小节令人费解的地方还是蛮多的。</p>
<p>通过这五条算法的规则，推导出该算法能够满足分布式锁的条件，并不是一目了然的。</p>
<p>关键是规则5，如何判断一个进程获取到了分布式锁的条件。一是要满足经过排序后，该进程的请求要位于请求队列的头节点；<br />
二是，原文中说</p>
<blockquote>
<p>\(P_i\) has received a message from every other process timestamped later than \(T_m\).</p>
</blockquote>
<p>也就是说该进程至少要从剩下的进程里收到一条比\(T_m\)还要大的消息。<br />
言外之意假设有进程P、Q、R，如果进程P想获取锁，那么除了它的命令请求要排在请求队列的头节点之外。
我们假设该命令的时间戳是\(T_m=10\)，那么它至少要收到从Q而来的比10还要晚的一条消息，再收到从R而来的比10还要晚的一条消息。<br />
满足上述两个条件之后，才进程P才可以认为它获取到了这把锁。</p>
<p>论文里并没有说这条更晚的消息是确认该命令的ACK还是其他。</p>
<blockquote>
<p><strong>参考</strong><br />
<a href="https://yang.observer/2020/07/26/time-lamport-logical-time/">计算机的时钟（二）：Lamport逻辑时钟</a></p>
</blockquote>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="lamport_logic_clock.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="lamport_clock_ana_behave.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="lamport_logic_clock.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="lamport_clock_ana_behave.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>




        <script type="text/javascript">
            window.playground_copyable = true;
        </script>


        <script src="elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="searcher.js" type="text/javascript" charset="utf-8"></script>

        <script src="clipboard.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="highlight.js" type="text/javascript" charset="utf-8"></script>
        <script src="book.js" type="text/javascript" charset="utf-8"></script>

        <!-- Custom JS scripts -->


    </body>
</html>
